//快速排序

#pragma once

//对序列 a[low...high] 快速排序
template <typename E>
void QSort(E a[],int low, int high)
{
    if(low >= high) return;

    //将序列 a[low...high] 划分成两个
    //子序列 a[low...i-1] 和 a[i+1...high]
    E p = a[low];
    int i = low,j = high;
    while(i < j){
        while (i < j && a[j] >= p) j--;
        a[i] = a[j];
        while(i < j && a[i] <= p) i++;
        a[j] = a[i];
    }
    a[i] = p;

    //分别对两个子序列快速排序
    QSort(a,low,i-1);
    QSort(a , i+1,high);
}

//对数组 a[n] 快速排序
template <typename E>
void QuickSort(E a[], int n)
{
    QSort(a,0,n-1);
}